package com.bigshen.algorithm.bStack.solution03MaxsumRange;

import java.util.Stack;

/**
 *
 *   5/4/3/2/1
 *   1/2/3/4/5
 *   5/2/3/1/4
 *   {5,3,2,4,1}
 *   最小值*区间和 (如果不是最小值，可以先继续累加)
 */
public class Solution02 {

    public int getMax(int[] array) {

        if (null == array) {
            return 0;
        }

        int max = 0;

        int[] sum = new int[array.length+1];
        // 区间和
        for (int i = 1; i < array.length+1; i++) {
            sum[i] = sum[i-1] + array[i-1];
        }

        // 区间最小值
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < array.length; i++) {

            while (!stack.isEmpty() && array[i] < array[stack.peek()]) {
                // 遍历到的数据比之前数据小，则之前数据可以计算一次 最小值*区间和
                int index = stack.pop();
                int left = stack.isEmpty() ? 0 : index;  // 区间 左侧下标
                int right = i; // 区间  右侧下标
                int current = array[index] * (sum[right] - sum[left]);  // 值 = 区间最小值 * 区间和
                System.out.println(String.format("得到上次最小值 %s 及区间 %s-%s， 区间和为 %s，区间和最小乘积为%s", array[index], left, right, sum[right] - sum[left], current));
                max = max > current ? max : current;
            }

            stack.push(i);

        }
        // 1/2/3/4/5
        while (!stack.isEmpty()) {
            // 遍历到的数据比之前数据小，则之前数据可以计算一次 最小值*区间和
            int index = stack.pop();
            int left = stack.isEmpty() ? 0 : index;  // 区间 左侧下标
            int right = array.length; // 区间  右侧下标
            int current = array[index] * (sum[right] - sum[left]);  // 值 = 区间最小值 * 区间和
            System.out.println(String.format("得到本次最小值 %s 及区间 %s-%s， 区间和为 %s，区间和最小乘积为%s", array[index], left, right, sum[right] - sum[left], current));
            max = max > current ? max : current;
        }

        return max;

    }

    public static void main(String[] args) {

//        int[] array = new int[]{5,4,3,2,1};
//        int[] array = new int[]{1,2,3,4,5};
        int[] array = new int[]{5,2,3,4,1};
//        int[] array = {5,2,3,4,1};

        System.out.println(new Solution02().getMax(array));

    }

}

